//
// pch.cpp
//

#include "pch.h"
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <iostream>
#include <cstring>
#include <string>
#include <fstream>
#include <streambuf>
#include <map>
#include <vector>
using namespace std;

struct EDGE {
	int from;
	int to;
	int len;
	string word;
	bool visited;
	int nxt;
} edge[100000];
int edgeNo;
int head[30];
map<string, bool> wordList;
bool reachable[30][30];
vector<string> chain;
vector<string> maxChain;
int maxLen;

void clear() {
	edgeNo = 0;
	maxLen = 0;
	wordList.clear();
	memset(reachable, 0, sizeof(bool) * 900);
	memset(head, 0, sizeof(int) * 30);
	chain.clear();
	maxChain.clear();
}

void AddEdge(int from, int to, int len, string word) {
	edge[++edgeNo].from = from;
	edge[edgeNo].to = to;
	edge[edgeNo].len = len;
	edge[edgeNo].word = word;
	edge[edgeNo].visited = false;
	edge[edgeNo].nxt = head[from];
	head[from] = edgeNo;
}

void init() {
	clear();
	for (int i = 0; i < 26; i++) {
		AddEdge(26, i, 0, "");
		AddEdge(i, 27, 0, "");
	}
}

int AddWord(string word, bool r) {
	if (wordList.find(word) != wordList.end()) return 0;
	int from = word[0] - 'a';
	int to = word[word.length() - 1] - 'a';
	if (!r && reachable[to][from]) return -1;
	wordList[word] = true;
	AddEdge(from, to, word.length(), word);
	reachable[from][to] = true;
	for (int i = 0; i < 26; i++) {
		if (reachable[i][from]) reachable[i][to] = true;
		if (reachable[to][i]) reachable[from][i] = true;
	}
	return 0;
}

int GetNum(int source, int end, int wordNum, int avoid) {
	//cout << source << ' ' << end << ' ' << wordNum << ' ' << avoid << endl;
	if (source == end) return wordNum >= 2 ? 1 : 0;
	if (source == avoid) return 0;
	int num = 0;
	for (int i = head[source]; i; i = edge[i].nxt) {
		//cout << edge[i].to << endl;
		if (edge[i].visited) continue;
		int to = edge[i].to;
		edge[i].visited = true;
		num += GetNum(to, end, wordNum + (edge[i].len > 0), avoid);
		edge[i].visited = false;
	}
	return num;
}


void GetAll(int source, int end, int wordNum, int avoid, vector<string>& result) {
	if (source == end && wordNum >= 2) {
		string merge("");
		for (unsigned int i = 0; i < chain.size(); i++)
			merge += chain[i] + ' ';
		result.push_back(merge);
	}
	if (source == avoid) return;
	for (int i = head[source]; i; i = edge[i].nxt) {
		if (edge[i].visited) continue;
		int to = edge[i].to;
		edge[i].visited = true;
		if (edge[i].len > 0) chain.push_back(edge[i].word);
		GetAll(to, end, wordNum + (edge[i].len > 0), avoid, result);
		if (edge[i].len > 0) chain.pop_back();
		edge[i].visited = false;
	}
}


void GetMostWords(int source, int end, int wordNum, int avoid) {
	if (source == end && wordNum >= 2) {
		if (wordNum > (int)maxChain.size())
			maxChain = chain;
	}
	if (source == avoid) return;
	for (int i = head[source]; i; i = edge[i].nxt) {
		if (edge[i].visited) continue;
		int to = edge[i].to;
		edge[i].visited = true;
		if (edge[i].len > 0) chain.push_back(edge[i].word);
		GetMostWords(to, end, wordNum + (edge[i].len > 0), avoid);
		if (edge[i].len > 0) chain.pop_back();
		edge[i].visited = false;
	}
}

void GetMostLetters(int source, int end, int wordNum, int letterNum, int avoid) {
	if (source == end && wordNum >= 2) {
		if (letterNum > maxLen) {
			maxChain = chain;
			maxLen = letterNum;
		}
	}
	if (source == avoid) return;
	for (int i = head[source]; i; i = edge[i].nxt) {
		if (edge[i].visited) continue;
		int to = edge[i].to;
		edge[i].visited = true;
		if (edge[i].len > 0) chain.push_back(edge[i].word);
		GetMostLetters(to, end, wordNum + (edge[i].len > 0), letterNum + edge[i].len, avoid);
		if (edge[i].len > 0) chain.pop_back();
		edge[i].visited = false;
	}
}

int gen_chains_all(vector<string> words, int len, vector<string>& result) {
	init();
	for (int i = 0; i < len; i++) {
		string word(words[i]);
		if (AddWord(word, 0)) {
			puts("word ring exists");
			return -1;
		}
	}
	int source = 26;
	int end = 27;
	int avoid = -1;
	GetAll(source, end, 0, avoid, result);
	return GetNum(source, end, 0, avoid);
}

int gen_chain_word(vector<string> words, int len, vector<string>& result,
	char head, char tail, char reject, bool enable_loop) {
	init();
	for (int i = 0; i < len; i++) {
		string word(words[i]);
		if (AddWord(word, enable_loop)) {
			puts("word ring exists");
			return -1;
		}
	}
	int source = (head == 0 ? 26 : head - 'a');
	int end = (tail == 0 ? 27 : tail - 'a');
	int avoid = (reject == 0 ? -1 : reject - 'a');
	GetMostWords(source, end, 0, avoid);
	result = maxChain;
	return maxChain.size();
}

int gen_chain_char(vector<string> words, int len, vector<string>& result,
	char head, char tail, char reject, bool enable_loop) {
	init();
	for (int i = 0; i < len; i++) {
		string word(words[i]);
		if (AddWord(word, enable_loop)) {
			puts("word ring exists");
			return -1;
		}
	}
	int source = (head == 0 ? 26 : head - 'a');
	int end = (tail == 0 ? 27 : tail - 'a');
	int avoid = (reject == 0 ? -1 : reject - 'a');
	GetMostLetters(source, end, 0, 0, avoid);
	result = maxChain;
	return maxChain.size();
}
